The present invention generally relates to finite state machines (FSMs), hierarchical finite state machines, and, in particular, to a method for specifying the behavior of a reactive entity or system.
A pure FSM includes a number of states and their outgoing transitions specified in a state diagram. When a state is inactive, all its (outgoing) transitions are disabled. When a state is active, all its (outgoing) transitions are enabled. Upon receiving an enabled valid event for a particular active state, a transition is triggered and an associated action is performed along with the transition. A transition may or may not change state. If a transition changes state, it makes the current state inactive, and makes another state active. If a transition can change to one of several possible states, which particular state to change to must be determined at run-time so that run-time deterministic behavior can be ensured. It should be understood that there are several variations of FSM semantics in existence. For the purposes of simplicity and clarity, the foregoing definition of FSM is adopted merely for illustration herein. However, this choice of definition of FSM should not be considered as restrictive.
Pure FSM has a number of disadvantages. For example, one undesirable restriction is that a pure FSM has no memory. Due to its lack of memory, the usage of a pure FSM is very limited. Since a state in a pure FSM contains no memory, any change or information about history, such as a simple counter, must be presented by defining additional states in order to maintain these changes. Given the infinite number of values that a counter may have, an infinite number of states would be required.
Extended finite state machines (EFSMs) or Register Automata add memory or data variables to each state to contain values, such as numbers and counters, to overcome the major problem of a pure FSM as described above. EFSMs are widely used to model various reactive systems.
When EFSMs are used to model some real world events or behavior, it is often found that a hierarchical of states or nested states are useful to reduce the number of states and to organize a complex set of states into a hierarchy. Statechart as part of the United Modeling Language (UML) and STATEMATE are some examples. See Bruce Powel Douglass, Doing Hard Time, Addison-Wesley, 1999. See also D. Harel et al., STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, Vol. 16, April 1990. Statechart is the term used herein to refer to a hierarchical finite state machine.
The benefits of statecharts are twofold. One is that the super-state provides a structuring mechanism to support layered abstraction of states. Layered abstraction is useful in specifying a complex system. It supports a stepwise refinement approach. In addition, with various layers, the system can be viewed at a different level of granularity at each layer. The other benefit is that by sharing some commonly used component states, the number of states can be greatly reduced.
Statechart supports two kinds of super-states. One kind of super-state is called OR-state. An OR-state can be decomposed into multiple sequential sub-states. An OR-state is alternatively called a “Sequential Composite State” as further described herein. The other kind of super-state is called AND-state. An AND-state can be decomposed into multiple parallel, orthogonal or concurrent sub-states (or regions as referred to by UML). An AND-state is alternatively called a “Parallel-AND Composite State” as further described herein.
However, to model many complex real world events and activities, these two kinds of super-states are not sufficient. One deficiency is that a statechart does not support “Parallel-OR Composite States” as further described herein.
A more significant deficiency is that a statechart does not support “Composite Transitions”. FSM traditionally supports only the concept of simple transitions. With a simple transition, one enabled event is sufficient to drive a state transition, namely moving from one state to another. However, in the real world, sometimes an object or an entity waits for several possible events, and only a certain logical combination of these events would trigger a state transition. The statechart attempts to solve this problem by forking and joining transitions and adding additional synchronization pseudo-states. However, the result of that approach is like spaghetti of transitions, and the spaghetti-like state diagram makes it very difficult to read and understand the meaning of a specification. From another perspective, reading a statechart with fork, join and pseudo-states is like reading a software code with many “goto” statements. A more elegant and structured way is needed.
Another significant deficiency is that a statechart does not support creating and destroying child FSMs dynamically or at run time. A traditional FSM is a sequential machine. It stays in one state and only handles those enabled events for that particular state. Events that are not considered valid for that particular state are ignored. For example, when a server object opens a customer record, and starts a session of editing (the editing session may have several states and each state can handle certain editing commands), while the server object is in the middle of editing one record, it typically cannot handle another record open request. This is because the server object would be in a state which can only accept a particular set of editing requests. However, in a highly sophisticated distributed computing environment, it is desirable that multiple sessions can be handled at the same time by a single server entity. It is also possible that each of these sessions may have child sessions, and a child session may have its own child sessions, hence, forming a tree of sessions at run time. Since how many sessions and child sessions are outstanding depend on what requests are received at run time, the number of states cannot be fixed at design time. Since a statechart only supports a static number of states, it cannot describe the behavior of such a dynamic server.
Traditionally, protocols between two interacting entities are defined in a FSM. However, since the number of states of a FSM is statically fixed at design time, FSM cannot be used to define complex protocols supporting a tree of communication sessions. For example, a customer talks to a support staff to place a new order (#2). While he is in the middle of placing the new order, the customer realizes that he needs to refer to another previously placed order (#1). So, the customer requests the support staff to dig into order #1 while temporarily putting the current order #2 on hold. After the customer is done with order #1, he continues with order #2. The customer may even want to open a third order before closing order #1 and #2. This kind of protocol supporting multiple concurrent sessions requires the support for a tree of sessions with each session defined as a FSM. This kind of protocol, however, cannot be defined as a single FSM due to its static nature.
Hence, it would be desirable to provide a method that is capable of extending and improving statecharts in order to accommodate the increasingly complex processing needs of reactive systems.